package chapter_2.merge;

import java.util.Arrays;

/**
 * (MergeSortWithSentinel).
 *
 * @author 汪文波(Wang Wenbo) wenboit@163.com
 * @notes Create on 2021-12-03 07:44
 */
public class MergeSortWithSentinel {

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        //int[] arr = {5, 2};
        MergeSortWithSentinel.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        MergeSortWithSentinel.sort(arr, 0, arr.length);
    }

    private static void sort(int[] arr, int p, int r) {
        // 索引范围：[p..r)
        if (p < (r - 1)) {
            // 防止溢出： p + r
            int q = p + (r - p) / 2;
            MergeSortWithSentinel.sort(arr, p, q);
            MergeSortWithSentinel.sort(arr, q, r);
            MergeSortWithSentinel.merge(arr, p, q, r);
        }
    }

    private static void merge(int[] arr, int p, int q, int r) {
        // 需要存储哨兵
        int n1 = q - p + 1;
        int n2 = r - q + 1;
        int[] left = new int[n1];
        int[] right = new int[n2];
        // 复制数据
        for (int i = 0; i < n1 - 1; i++) {
            left[i] = arr[p + i];
        }
        for (int i = 0; i < n2 - 1; i++) {
            right[i] = arr[q + i];
        }
        // 存储哨兵
        left[n1 - 1] = Integer.MAX_VALUE;
        right[n2 - 1] = Integer.MAX_VALUE;

        // 对 n = r - p 个数排序
        int i = 0, j = 0;
        for (int k = p; k < r; k++) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
        }
    }

}
